#pragma once
#include<bits/stdc++.h>

template <typename Comparable>
class BinarySearchTree
{
public:
    BinarySearchTree();
    BinarySearchTree(const BinarySearchTree & rhs);
    BinarySearchTree(BinarySearchTree && rhs);
    ~BinarySearchTree();

    const Comparable &findMin() const;
    const Comparable &findMax() const;
    bool contains(const Comparable & x)const;
    bool isEmpty()cosnt;
    void printTree(ostream & out=cout) const;
    void makeEmpty();
    void insert(const Comparable & x);
    void insert(Comparable && x);
    void remove(const Comparable & x);

    BinarySearchTree & operator = (const BinarySearchTree & rhs);
    BinarySearchTree & operator = (BinarySearchTree && rhs);

private:
    struct BinaryNode
    {
	Comparable element;
	BinaryNode *left;
	BinaryNode *right;
	binarynode (const Comparable & theElement,BinaryNode *lt,BinaryNode *rt):element{std::move(theElement)},left[lt],right{rt}{]
    };

    Binary *root;
    Comparator isLessThan;
    void insert(const Object & x, BinaryNode *& t);
    void insert(Object && x, BinaryNode *& t);
    void remove(const Object & x, BinaryNode *& t);
    BinaryNode * findMin(BinaryNode *t) const;
    BInaryNode * findMax(BinaryNode *t) const;
    bool contains(const Object & x, BinaryNode *t) const
    {
	if(t==NULL)
	    return false;
	else if(isLessThan(x,t->element))
	    return contains(x,t->left);
	else if(isLessThan(t->element,x))
	    return contains(x,t->right);
	else
	    return true;//match
    };
void insert(const Comparable & x)
{
    insert(x,root);
}

void remove(const Comparable & x)
{
    remove(x,root);
}

template <typename Object,typename Comparator=less<Object>>
class BinarySearchTree
{
    public:
      BinarySearchTree();
      BinarySearchTree(const BinarySearchTree & rhs);
      BinarySearchTree(BinarySearchTree && rhs);
      ~BinarySearchTree();

      const Object & findMin() const;
      const Object & findMax() const;
      bool contains(const Object & x) const;
      bool isEmpty() const;
      void printTree(ostream & out = cout) const;

      void makeEmpty();
      void insert(const Object & x);
      void insert(Object && x);
      void remove(const Object & x);

      BinarySearchTree & operator=(const BinarySearchTree & rhs);
      BinarySearchTree & operator=(BinarySearchTree && rhs);

    private:
      struct BinaryNode
      {
          Object element;
          BinaryNode *left;
          BinaryNode *right;

          BinaryNode(const Object & theElement, BinaryNode *lt, BinaryNode *rt)
            : element{std::move(theElement)}, left{lt}, right{rt} {}
      };

      BinaryNode *root;
      Comparator isLessThan;
      void insert(const Object & x, BinaryNode * & t);
      void insert(Object && x, BinaryNode * & t);
      void remove(const Object & x, BinaryNode * & t);
      BinaryNode * findMin(BinaryNode *t) const;
      BinaryNode * findMax(BinaryNode *t) const;
      bool contains(const Object & x, BinaryNode *t) const
      {
          if(t==NULL)
             return false;
          else if(isLessThan(x,t->element))
             return contains(x,t->left);
          else if (isLessThan(t->element,x))
             return contains(x,t->right);
          else  
             return true; //match  
      };
      void makeEmpty(BinaryNode * & t);
      void printTree(BinaryNode *t, ostream & out) const;
      BinaryNode * clone(BinaryNode *t) const;
};
BinaryNode * findMin(BinaryNode *t) const
{
    if(t == NULL)
       return NULL;
    if(t->left == NULL)
       return t;
    return findMin(t->left);
}
BinaryNode * findMax(BinaryNode *t) const
{
    if(t != NULL)
       while(t->right != NULL)
          t = t->right;
    return t;
}
void insert(const Comparable & x,BinaryNode * & t)
{
    if(t == NULL)
       t=new BinaryNode{x,NULL,NULL};
    else if (x< t->element)
       insert(x,t->left);
    else if(t->element < x)
       insert(x, t->right);
    else
       ; //duplicate;do nothing.
}

//intrenal method to insert into a subtree.
//x is the item to insert by moving.
//t is the node that roots the subtree.
//set the new root of the subtree.
void insert(Comparable && x,BinaryNode * & t)
{
    if(t == NULL)
       t = new BinaryNode{ std::move(x),NULL,NULL};
    else if(x< t->element)
       insert(std::move(x),t->left);
    else if(t->element < x)
       insert(std::move(x),t->right);
    else
       ; //dupicate;do nothing
} 

//internal method to remove from a subtree.
//x is the item to remove.
//t is the node that roots the subtree.
//set the new root of the subtree.
void remove(const Comparable & x, BinaryNode * & t)
{
    if(t==NULL)
       return; //item not found;do nothng
    if(x< t->element)
       remove(x,t->left);
    else if(t->element < x)
       remove(x,t->right);
    else if(t->left != NULL && t->right!==NULL) //two children
    {
        t->element = findMin(t->right)->element;
        remove(t->element,t->right);
    }
    else
    {
        BinaryNode *oldNode = t;
        t=(t->left != NULL)?t->left:t->right;
        delete oldNode;
    }
}

//destructor for the tree.
~BinarySearchTree()
{
    makeEmpty();
}
//internal method to make subtree empty.
void makeEmpty(BinaryNode * & t)
{
    if(t != NULL)
    {
        makeEmpty(t->left);
        makeEmpty(t->right);
        delete t;
    }
    t = NULL;
}

//copy constructor
BinarySearchTree(const BinarySearchTree & rhs) : root{NULL}
{
    root=clone(rhs.root);
}

//internal method to clone subtree.
BinaryNode * clone(BinaryNode *t) const
{
    if(t == NULL)
       return NULL;
    else
       return new BinaryNode{t->element,clone(t->left),clone(t->right)};
}

    
		
